package leetcode_interview;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class I0104 {

    //    输入："tactcoa"
//    输出：true（排列有"tacocat"、"atcocta"，等等）
    public boolean canPermutePalindrome1(String s) {
//        int[] useDict = new int[26];
        Map<Character, Integer> dict = new HashMap<>();
        int oddCount = 0;
        char[] chars = s.toCharArray();
        for (char c : chars) {
            dict.put(c, dict.getOrDefault(c, 0) + 1);
        }
//        for (int useCount : useDict) {
//            if (useCount % 2 != 0)
//                oddCount++;
//        }
        for (Map.Entry<Character, Integer> e : dict.entrySet()) {
            if (e.getValue() % 2 == 1)
                oddCount++;
        }
        if (oddCount <= 1)
            return true;
        return false;
    }

    // 回文串 最多只有一个奇数个的字符（奇数长的字符串） 这个字符放在字符串中间
    // 偶数长度的字符串
    // 通过偶数删除所有偶数个
    public boolean canPermutePalindrome(String s) {
        Set<Character> dict = new HashSet<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (dict.contains(c))
                dict.remove(c);
            else
                dict.add(c);
        }
        return dict.size() <= 1;
    }
}
